The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We analyze a separation procedure for Mixed-Integer Programs related to the work of Gomory and Johnson on interpolated subadditive functions. This approach has its roots in the Gomory-Johnson characterization on the master cyclic group polyhedron. To our knowledge, the practical benefit that can be obtained by embedding interpolated subadditive cuts in a cutting plane algorithm was not investigated...
How difficult is, in practice, to optimize exactly over the first Chvàtal closure of a generic ILP? Which fraction of the integrality gap can be closed this way, e.g., for some hard problems in the MIPLIB library? Does it pay to insist on rank-1 Chvàtal-Gomory inequalities until no such inequality is violated, or one should better follow the usual strategy of generating (mixed-integer) Gomory cuts...
We present a scheme for generating new valid inequalities for mixed integer programs by taking pair-wise combinations of existing valid inequalities. Our scheme is related to mixed integer rounding and mixing. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that lead to a manageable...
We study the ratio between the minimum size of an odd cycle vertex transversal and the maximum size of a collection of vertex-disjoint odd cycles in a planar graph. We show that this ratio is at most 10. For the corresponding edge version of this problem, Král and Voss [7] recently proved that this ratio is at most 2; we also give a short proof of their result.
In the edge-disjoint cycle packing problem we are given a graph G and we have to find a largest set of edge-disjoint cycles in G. The problem of packing vertex-disjoint cycles in G is defined similarly. The best approximation algorithms for edge-disjoint cycle packing are due to Krivelevich et al. [16], where they give an -approximation for undirected graphs and an $O(\sqrt{n})$...
We give a new, algorithmic proof for the maximum even factor formula which can be converted into a polynomial time combinatorial algorithm to solve the maximum even factor problem. In several aspects, the approach is similar to Edmonds’ Matching Algorithm, but there is a significant difference.
We consider a generic paradigm to design improved PTAS for linear programming relaxations of combinatorial optimization problems. For the case of the uncapacitated facility location problem, the scheduling problem R ∥ Cmax and the set covering problem we substantially improve the running time dependence on ε from the previously known O(1/ε2) to O(1/ε)...
We are given an undirected simple graph G = (V,E) with edge capacities , e ∈ E, and a set K ⊆ V2 of commodities with demand values d(s,t)εℤ, (s, t) ∈ K. An unsplittable shortest path routing (USPR) of the commodities K is a set of flow paths Φ(s,t), (s, t) ∈ K, such that each Φ(s,t) is the unique shortest (s, t)-path for commodity (s...
We consider important generalizations of a wide class of traditional deterministic inventory and facility location models that we call inventory/facility location models with market selection. Instead of the traditional setting, we are given a set of markets, each specified by a sequence of demands and associated with a revenue. Decisions are made in two stages. We first make a decision of what markets...
In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well–known combinatorial optimization problems, as well as problems in control theory. For instance, they include Max–3–Cut where the Laplacian matrix is positive semidefinite (in particular, some of the...
Lovász and Schrijver [9] have constructed semidefinite relaxations for the stable set polytope of a graph G = (V,E) by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most α(G) steps, where α(G) is the stability number of G. Two other hierarchies of semidefinite bounds for the stability number have been proposed by Lasserre [4],[5] and by de Klerk and...
We describe the semidefinite analog of the vector packing problem, and show that the semidefinite programming relaxations for Maxcut [10] and graph coloring [17] are in this class of problems. We extend a method of Bienstock and Iyengar [5] which was based on ideas from Nesterov [25] to design an algorithm for computing ε-approximate solutions for this class of semidefinite programs. Our algorithm...
We present a short geometric proof for the price of anarchy results that have recently been established in a series of papers on selfish routing in multicommodity flow networks. This novel proof also facilitates two new types of results: On the one hand, we give pseudo-approximation results that depend on the class of allowable cost functions. On the other hand, we derive improved bounds on the inefficiency...
We consider unrelated parallel machine scheduling problems with the objective to minimize the schedule makespan. In addition to its machine-dependence, the processing time of any job is also dependent on the usage of a scarce renewable resource. An amount of k units of that resource, e.g. workers, can be distributed over the jobs in process, and the more of that resource is allocated to a job, the...
We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions are analyzed. Using linear programming techniques, borrowed from the single machine case,...
We introduce unique sink orientations of grids as digraph models for many well-studied problems, including linear programming over products of simplices and generalized linear complementarity problems over P-matrices (PGLCP). We investigate the combinatorial structure of such orientations and develop randomized algorithms for finding the sink. We show that the orientations arising from PGLCP satisfy...
We construct a class of abstract objective functions on the cube, such that the algorithm BottomAntipodal takes exponentially many steps to find the maximum. A similar class of abstract objective functions is constructed for the process BottomTop, also requiring exponentially many steps.
A symmetric matrix A is said to be sign-nonsingular if every symmetric matrix with the same sign pattern as A is nonsingular. Hall, Li and Wang showed that the inertia of a sign-nonsingular symmetric matrix is determined uniquely by its sign pattern. The purpose of this paper is to present an efficient algorithm for computing the inertia of such matrices. The algorithm runs in O(nm) time for a symmetric...
In the Max FS problem, given an infeasible linear system Ax ≥ b, one wishes to find a feasible subsystem containing a maximum number of inequalities. This NP-hard problem has interesting applications in a variety of fields. In some challenging applications in telecommunications and computational biology one faces very large Max FS instances with up to millions of inequalities in thousands...
Clique separators in graphs are a helpful tool used by Tarjan as a divide-and-conquer approach for solving various graph problems such as the Maximum Weight Stable Set (MWS) Problem, Coloring and Minimum Fill-in but few examples are known where this approach was used. We combine decomposition by clique separators and by homogeneous sets and show that the resulting binary tree gives an efficient way...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.